#include <iostream>
#include <vector>
#include <string>
#include <memory>
#include <iterator>

using namespace std;

//定义迭代器所需要的部分
template <class BidirectionalIterator, class T, class Reference, 
          class Distance>
class reverse_bidirectional_iterator {
  typedef reverse_bidirectional_iterator<BidirectionalIterator, T, Reference,
                                         Distance> self;
protected:
    BidirectionalIterator current;
public:
    typedef bidirectional_iterator_tag iterator_category;
    typedef T                          value_type;
    typedef Distance                   difference_type;
    typedef T*                         pointer;
    typedef Reference                  reference;

    reverse_bidirectional_iterator() {}
    explicit reverse_bidirectional_iterator(BidirectionalIterator x)
     : current(x) {}
    BidirectionalIterator base() const { return current; }
    Reference operator*() const {
        BidirectionalIterator tmp = current;
        return *--tmp;
    }
    pointer operator->() const { return &(operator*()); }
    self& operator++() {
        --current;
        return *this;
    }
    self operator++(int) {
        self tmp = *this;
        --current;
        return tmp;
    }
    self& operator--() {
        ++current;
        return *this;
    }
    self operator--(int) {
        self tmp = *this;
        ++current;
        return tmp;
    }
}; 

template <class T>
struct _list_node {
    typedef void* void_pointer;//定义一个类型别名 void_pointer ，为指向void 的指针
    void_pointer next;//指向下一个节点的指针
    void_pointer prev;//指向前一个节点的指针
    T date;//存储节点实际数据的成员，类型有模板参数T决定
};

//
//list不同与以往的数组的指针，可以++，-- ,所以要有自己的迭代器
//

//T:元素类型，Ref:引用类型，Ptr：指针类型
template<class T, class Ref, class Ptr>
struct _list_iterator {
    typedef _list_iterator<T, T&, T*> iterator;
    typedef _list_iterator<T, const T&, const T*> const_iterator;
    typedef _list_iterator<T, Ref, Ptr> self;

    typedef bidirectional_iterator_tag iterator_category;//将自己的iterator_category定义为bidirectional_iterator_tag
    typedef T value_type;
    typedef Ptr pointer;
    typedef Ref reference;
    typedef _list_node<T>* link_type;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;

    link_type node;

    _list_iterator(link_type x) : node(x) {}//从节点指针构造
    _list_iterator(){}//默认指针
    _list_iterator(const iterator& x) : node(x.node){}//拷贝构造

    bool operator==(const self& x) const {return node == x.node;}
    bool operator!=(const self& x) const {return node != x.node;}
    reference operator*() const {return (*node).date;}//返回节点数据的引用

    pointer operator->() const {return &(operator*());}//返回节点数据的指针

    //前置++
    self& operator++() {//移动到下一个节点（通过next指针），返回当前迭代器的引用
        node = (link_type)((*node).next);
        return *this;
    }

    //后置++，为上面那个的重载版本
    self operator++(int) {//保存参数int标识这是后置++
        self tmp = *this;//保存当前的状态
        ++*this;//调用前置++推进指针
        return tmp;//返回旧值
    }

    //前置--
    self operator--() {//移动到上一个节点（通过prev指针），返回当前迭代器的引用
        node = (link_type)((*node).prev);
        return *this;
    }

    //后置--
    self operator--(int) { 
        self tmp = *this;
        --*this;
        return tmp;
    }
};

//声明_list_iterator是双向迭代器（可以通过++和--移动）
template<class T, class Ref, class Ptr>
inline bidirectional_iterator_tag
iterator_category(const _list_iterator<T, Ref, Ptr>&) {
    return bidirectional_iterator_tag();//返回一个临时对象。这是空类
}

//元素类型萃取，提取迭代器的指向的元素类型T
template<class T, class Ref, class Ptr>
inline T*
value_type(const _list_iterator<T, Ref, Ptr>&) {
    return 0;//通过返回T*类型的空指针（0）按时类型信息
}

//举例类型萃取，声明迭代器举例的类型为ptrdiff_t
template<class T, class Ref, class Ptr> 
inline ptrdiff_t*
distance_type(const _list_iterator<T, Ref, Ptr>&) {
    return 0;
}

template <class T, class Alloc = allocator<T>>
class simple_alloc {
public:
    using RealAlloc = typename std::allocator_traits<Alloc>::template rebind_alloc<T>;

    static T* allocate(size_t n) {
        RealAlloc alloc;
        return std::allocator_traits<RealAlloc>::allocate(alloc, n);
    }

    static void deallocate(T* p, size_t n) {
        RealAlloc alloc;
        std::allocator_traits<RealAlloc>::deallocate(alloc, p, n);
    }
};

template<class T, class Alloc = allocator<T>>
class list {
protected:
    typedef void* void_pointer;
    typedef _list_node<T> list_node;
    typedef simple_alloc<list_node, Alloc> list_node_allocator;

public:
    typedef T value_type;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef list_node* link_type;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;

protected:
    link_type node;	// 成员变量__list_node<T>* node

    using NodeAlloc = typename allocator_traits<Alloc>::template rebind_alloc<_list_node<T>>;
    NodeAlloc node_alloc_;  // 分配器实例
public:
    typedef _list_iterator<T, T&, T*> iterator;//特定迭代器
    typedef _list_iterator<T, const T&, const T*> const_iterator;

    //定义两个反向迭代器类型，
    // typedef reverse_iterator<const_iterator> const_reverse_iterator;//只读版本的反向迭代器
    // typedef reverse_iterator<iterator> reverse_iterator;//可修改元素的反向迭代器

    typedef reverse_bidirectional_iterator<const_iterator, value_type,
    const_reference, difference_type>
    const_reverse_iterator;
    typedef reverse_bidirectional_iterator<iterator, value_type, reference,
    difference_type>
    reverse_iterator; 

protected:
    //新创造节点
    link_type get_node() {return list_node_allocator::allocate(sizeof(list_node));}

    //释放节点
    void put_node(link_type p) {list_node_allocator::deallocate(p, sizeof(list_node));}

    //创造一个节点
    link_type create_node(const T& x) {
        link_type p = get_node();
        try {
            // 使用 allocator_traits 的 construct 方法
            std::allocator_traits<NodeAlloc>::construct(
            node_alloc_,  // 分配器实例
            &(p->date),   // 成员变量名（根据错误提示使用date）
            x             // 构造参数
        );
        }
        catch(...) {
            put_node(p);  // 如果构造失败，释放内存
            throw;        // 重新抛出异常
        }
        return p;
    }

    //销毁一个节点
    void destroy_node(link_type p) {
        _Destroy(&p->date);
        put_node(p);
    }

protected:
    //
    //创造一个新的节点，作为头节点，同时也是结束的节点，因为是双向两包
    //并将next和prev均指向自己
    //

    //创建一个新链表
    void empty_initialize() {
        node = get_node();
        node->next = node;
        node->prev = node;
    }

    //创建一个N个节点并且填充数据
    void fill_initialize(size_type n, const T& value) {
        empty_initialize();
        try {
            insert(begin(), n, value);
        }
        catch(...) {
            put_node(node);
        }
    }

    //范围初始化
    // void range_initialize(InputIterator first, InputIterator last) {
    //     empty_initialize();
    //     try {
    //         insert(begin(), first, last);
    //     }
    //     catch(...) {
    //         clear();
    //         put_node(node);
    //     }
    // }

    //对于上面范围初始化的重载
    void range_initialize(const T* first, const T* last) {
        empty_initialize();
        try {
        insert(begin(), first, last);
        }
        catch(...) {
            clear();
            put_node(node);
        }
    }

    void range_initialize(const_iterator first, const_iterator last) {
        empty_initialize();
        try {
            insert(begin(), first, last);
        }

        catch(...) {
            clear();
            put_node(node);
        }
    }

public:
    //构造函数
    list() {empty_initialize();}

    iterator begin() {return (link_type)((*node).next);}//返回头节点
    const_iterator begin() const {return (link_type)((*node).next);}
    iterator end() {return node;}//返回最后一个节点
    const_iterator end() const {return node;}
    reverse_iterator rbegin() {return reverse_iterator(end());}//返回反转链表后的头节点
    const_reverse_iterator rbegin() const {return const_reverse_iterator(end());}
    reverse_iterator rend() {return reverse_iterator(begin());}//返回反转链表后的最后一个节点
    const_reverse_iterator rend() const {return const_reverse_iterator(begin());}
    bool empty() const {return node->next == node;}//判断当前链表是否为空
    size_type size() const {//判断当前链表的大小
        size_type result = 0;
        distance(begin(), end(), result);//通过遍历得到size
        return result;
    }
    size_type max_size() const {return size_type(-1);}
    reference front() {return *begin();}//先获得迭代器，然后调用迭代器的operator*()函数
    const_reference front() const {return *begin();}//访问首元素
    reference back() {return *(--end());}//前闭后开原则，所以尾迭代器要先--。然后调用operator*()函数
    const_reference back() const {return *(--end());}//访问尾元素
    void swap(list<T, Alloc>& x) {std::swap(node, x.node);}//交换两个节点的位置
    //指定位置插入，实际上就是双向链表插入
    //返回新插入的位置
    iterator insert(iterator position, const T& x) {
        link_type tmp = create_node(x);
        tmp->next = position.node;
        tmp->prev = position.node->prev;
        (link_type(position.node->prev))->next = tmp;
        position.node->prev = tmp;
        return tmp;
    }
    //按照默认类型插入
    iterator insert(iterator position) {return insert(position, T());}

    //对于插入函数的不同情况进行重载
    void insert(iterator pos, size_type n, const T& x);
    void insert(iterator pos, int n, const T& x) {
        insert(pos, (size_type)n, x);
    }
    void insert(iterator pos, long n, const T& x) {
        insert(pos, (size_type)n, x);
    }

    //在链表的头部插入一个节点
    void push_front(const T& x) {insert(begin(), x);}
    //在链表的尾部插入一个节点
    void push_back(const T& x) {insert(end(), x);}

    //就是双向链表的删除特定节点，并且返回删除节点的下一个节点
    iterator erase(iterator position) {
        link_type next_node = link_type(position.node->next);
        link_type prev_node = link_type(position.node->prev);
        prev_node->next = next_node;
        next_node->prev = prev_node;
        destroy_node(position.node);
        return iterator(next_node);
    }
    iterator erase(iterator first, iterator last);
    void resize(size_type new_size, const T& x);//重新定义链表的大小
    void resize(size_type new_size) {resize(new_size, T());}
    void clear();//清空链表
    void pop_front() {erase(begin());}//删除头节点下一个节点
    void pop_back() {
        iterator tmp = end();
        erase(--tmp);//删除尾的上一个节点
    }
    //重载构造函数
    list(size_type n, const T& value) {fill_initialize(n, value);}//独自的fill_initialize，不能使用通用的
    list(int n, const T& value) {fill_initialize(n, value);}
    list(long n, const T& value) {fill_initialize(n, value);}
    explicit list(size_type n) {fill_initialize(n, T());}

    template <class InputIterator>
    list(InputIterator first, InputIterator last) {
         range_initialize(first, last);
    }

    list(const list<T, Alloc>& x) {
        range_initialize(x.begin(), x.end());
    }
    ~list() {//析构函数
        clear();		// 删除双向链表中的每个元素
        put_node(node);	// 删除头结点
    }
    list<T, Alloc>& operator=(const list<T, Alloc>& x);//拷贝构造函数
protected:
    //将[first, last）的链表插入到position之前的位置
    void transfer(iterator position, iterator first, iterator last) {
        if(position != last) {
            (*(link_type((*last.node).prev))).next = position.node;
            (*(link_type((*first.node).prev))).next = last.node;
            (*(link_type((*position.node).prev))).next = first.node;  
            link_type tmp = link_type((*position.node).prev);
            (*position.node).prev = (*last.node).prev;
            (*last.node).prev = (*first.node).prev; 
            (*first.node).prev = tmp;
        }
    }
public:
    //拼接将x的[first, last)数据拼接到position之前
    void splice(iterator position, list& x) {
        if(!x.empty()) {
            transfer(position(), x.begin(), x.end());
        }
    }
    //将i拼接到positon之前的位置
    void splice(iterator position, list&, iterator i) {
        iterator j = i;
        ++j;
        if(position == i || position == j) return;
        transfer(position, i, j);
    }
    void splice(iterator position, list&, iterator first, iterator last) {
        if (first != last) 
        transfer(position, first, last);
    }
    void remove(const T& value);//删除特定值的所有节点
    void unique();//删除连续重复值
    void merge(list& x);//合并有序链表
    void reverse();//反转链表
    void sort();//对链表进行从小到大进行排序

};

//重载==用于比较两个链表是否想等
template <class T, class Alloc>
inline bool operator==(const list<T, Alloc>& x, const list<T, Alloc>& y) {
    typedef typename list<T, Alloc>::link_type link_type;
    link_type e1 = x.node;
    link_type e2 = y.node;
    link_type n1 = (link_type) e1->next;
    link_type n2 = (link_type) e2->next;
    for(; n1 != e1 && n2 != e2; n1 = (link_type)n1->next, n2 = (link_type)n2->next) {
        if(n1->date != n2->date) {
            return false;
        }
    }
    return n1 == e1 && n2 == e2;
}

template<class T, class Alloc>
inline bool operator<(const list<T, Alloc>& x, const list<T, Alloc>& y) {
    return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
}

template <class T, class Alloc>
inline void swap(list<T, Alloc>& x, list<T, Alloc>& y) {
  x.swap(y);
}

template <class T, class Alloc>
void list<T, Alloc>::insert(iterator position, size_type n, const T& x) {
  for ( ; n > 0; --n)
    insert(position, x);
}

template <class T, class Alloc>
typename list<T, Alloc>::iterator list<T, Alloc>::erase(iterator first, iterator last) {
    while(first != last) {
        erase(first++);
    }
    return last;
}

template <class T, class Alloc>
void list<T, Alloc>::resize(size_type new_size, const T& x) {
    iterator i = begin();
    size_type len = 0;
    for(; i != end() && len < new_size; i++, len++) {
        ;
    }
    if(len == new_size) {
        erase(i, end());
    }
    else {
        insert(end(), new_size - len, x);
    }
}

//就是链表的删除
template <class T, class Alloc>
void list<T, Alloc>::clear() {
    link_type cur = (link_type) node->next;
    while(cur != node) {
        link_type tmp = cur;
        cur = (link_type) cur->next;
        destroy_node(tmp);
    }
    node->next = node;
    node->prev = node;
}

template <class T, class Alloc>
list<T, Alloc>& list<T, Alloc>::operator=(const list<T, Alloc>& x) {
    if (this != &x) {
        iterator first1 = begin();
        iterator last1 = end();
        const_iterator first2 = x.begin();
        const_iterator last2 = x.end();
    while (first1 != last1 && first2 != last2) *first1++ = *first2++;
        if (first2 == last2)
            erase(first1, last1);
        else
            insert(last1, first2, last2);
    }
  return *this;
}

//
//遍历所有节点，并变删除值为value的元素
//
template <class T, class Alloc>
void list<T, Alloc>::remove(const T& value) {
    iterator first = begin();
    iterator last = end();
    while(first != last) {
        iterator next = first;
        ++next;
        if(*first == value) {
            erase(first);
        }
        first = next;
    }
}

//
//删除连续相同的元素值，例如<1, 1, 2, 2, 1, 3>变成<1, 2, 1, 3>
//
template <class T, class Alloc>
void list<T, Alloc>::unique() {
    iterator first = begin();
    iterator last = end();
    if(first == last) return;
    iterator next = first;
    while(++next != last) {
        if(*first == *next) {
            erase(next);
        }
        else {
            first = next;
        }
        next = first;
    }
}

//
//将x的所有内容合并到自己本身
//前提条件，两个链表都必须是排序过的
//
template <class T, class Alloc>
void list<T, Alloc>::merge(list<T, Alloc>& x) {
    iterator first1 = begin();
    iterator last1 = end();
    iterator first2 = x.begin();
    iterator last2 = x.end();
    while(first1 != last1 && first2 != last2) {
        if(*first2 < *first1) {
            iterator next = first2;
            transfer(first1, first2, ++next);
            first2 = next;
        }
        else {
            ++first1;
        }
    }
    if(first2 != last2) transfer(last1, first2, last2);
}

//
//逆置
//
template <class T, class Alloc>
void list<T, Alloc>::reverse() {
    if(node->next == node || link_type(node->next)->next == node) {
        return;
    }
    iterator first = begin();
    ++first;
    while(first != end()) {
        iterator old = first;
        ++first;
        transfer(begin(), old, first);
    }
}

//
//针对list的排序，不使用通用的sort排序，原因如下：
//通用的sort排序只接受RandomAccessIterator
//特定quick sort
//
template <class T, class Alloc>
void list<T, Alloc>::sort() {
    if(node->next == node || link_type(node->next)->next == node) {
        return;
    }
    list<T, Alloc> carry;
    list<T, Alloc> counter[64];
    int fill = 0;
    while(!empty()) {
        carry.splice(carry.begin(), *this, begin());//每次获取当前的第一个元素
        int i = 0;
        while(i < fill && !counter[i].empty()) {//判断数组中是否存在已经排序好的数据，并且没有到数组结束为止
            counter[i].merge(carry);//将carry的元素按序合并到数组i的链表中
                                    //其中carry储存可能是获得的一个元素，也可能是排序好的元素，完成后carry为空
            carry.swap(counter[i++]);//carry存储排序好的内容，并将数组i的链表清空，i指向下一个位置
        }
        carry.swap(counter[i]);//carry的内容存储到数组列表i中
        if(i == fill) ++fill;//更新数组的最大下标
    }

    for(int i = 1; i < fill; i++) {//将数组列表i - 1排序好的内容合并到数组链表i中，两个已经是有序的了
        counter[i].merge(counter[i - 1]);//调用前自己的链表为空，并与排序好的进行交换
    }
}

int main() 
{
    // 定义一个存储 double 类型的链表（适合数值计算）
    list<double, allocator<double>> myList;

    // 在链表尾部插入数据
    myList.push_back(1.1);
    myList.push_back(2.2);
    myList.push_back(3.3);
    myList.push_back(4.4); // {1.1, 2.2, 3.3, 4.4}

    // 在链表头部插入数据
    myList.push_front(0.0); // {0.0, 1.1, 2.2, 3.3, 4.4}

    // 遍历链表（C++11 范围 for 循环）
    for (double val : myList) {
        std::cout << val << " ";
    }
    // 输出: 0.0 1.1 2.2 3.3 4.4

    // 删除特定值
    myList.remove(2.2); // {0.0, 1.1, 3.3, 4.4}

    // 排序（升序）
    myList.sort(); // {0.0, 1.1, 3.3, 4.4}

    return 0;
}
